package com.li.tree;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Stack;

public class BTree {
	private static Stack<Integer> pathList = new Stack<Integer>();
	
	public static void main(String[] args) {
//		Node root = creatBTree();
//		MLR(root);
//		System.out.println();
//		levelTravel(root);
//		System.out.println();
//		Node father = findCommonFather(root, 2, 7);
//		System.out.println(father.value);
		
		
//		Node2 node1 = new Node2(1);
//		Node2 node2 = new Node2(2);
//		Node2 node3 = new Node2(3);
//		Node2 node4 = new Node2(4);
//		Node2 node5 = new Node2(5);
//		Node2 node6 = new Node2(6);
//		Node2 node7 = new Node2(7); 
//		
//		node5.left = node3;
//		node3.parent = node5;
//		node5.right = node7;
//		node7.parent = node5;
//		node3.left = node2;
//		node2.parent = node3;
//		node2.left = node1;
//		node1.parent = node2;
//		node3.right = node4;
//		node4.parent = node3;
//		node7.left = node6;
//		node6.parent = node7;
//		Node2 node = findCommonFather2(node5, node2, node6);
//		if(node!=null){
//			System.out.println(node.value);
//		}else{
//			System.out.println(" no common father");
//		}
		
		Node node1 = new Node(1);
		Node node2 = new Node(2);
		Node node3 = new Node(3);
		Node node4 = new Node(4);
		Node node5 = new Node(5);
		Node node6 = new Node(6);
		Node node7 = new Node(7); 
		Node node8 = new Node(8); 
		
		node5.left = node3;
		node5.right = node8;
		node8.left = node7;
		node3.left = node2;
		node2.left = node1;
		node3.right = node4;
		node7.left = node6;
//		Node node = findCommonFather3(node5, node2, node1);
//		if(node!=null){
//			System.out.println(node.value);
//		}else{
//			System.out.println(" no common father");
//		}
//		Stack<Integer> list = new Stack<Integer>();
//		findPath(node5, 6, list);
//		for(Integer data : pathList){
//			System.out.print(data+" ");
//		}
		
//		System.out.println(getMaxDeph(node5));
//		System.out.println(getMinDeph(node5));
//		System.out.println(numOfNode(node5));
//		System.out.println(numOfLeaf(node5));
//		System.out.println(getLevelNumOfNode(node5, 3));
//		System.out.println(isBalanced(node5));
//		System.out.println(isAllTree(node3));
//		System.out.println(isSimTree(node5, node3));
//		System.out.println(isMirror(node5, node5));
//		Node root = convertTree(node5);
//		levelTravel(root);
		
//		Node root = buildTreeByPreAndMid(new int[]{5,3,2,1,4,8,7,6}, new int[]{1,2,3,4,5,6,7,8});
//		LMR(root);
//		System.out.println();
//		MLR(root);
//		Node root = buildTreeByMidAndPost(new int[]{1,2,3,4,5,6,7,8}, new int[]{1,2,4,3,6,7,8,5});
//		LMR(root);
//		System.out.println();
//		LRM(root);
//		Node root = buildTreeByMidAndLevel(new int[]{1,2,3,4,5,6,7,8}, new int[]{5,3,8,2,4,7,1,6});
//		LMR(root);
//		System.out.println();
//		levelTravel(root);
//		Node root = insertNode(node5, 9);
//		levelTravel(root);
		//findAllPath(node5, 26);
		//findNodeBetweenAAndB(node5, 2, 7);
		System.out.println(isBST(node5));
	}
	
	/**
	 * 创建排序二叉树
	 * @return
	 */
	public static Node creatBTree(){
		Node node1 = new Node(1);
		Node node2 = new Node(2);
		Node node3 = new Node(3);
		Node node4 = new Node(4);
		Node node5 = new Node(5);
		Node node6 = new Node(6);
		Node node7 = new Node(7); 
		
		node5.left = node3;
		node5.right = node7;
		node3.left = node2;
		node2.left = node1;
		node3.right = node4;
		node7.left = node6;
		return node5;
	}
	/**
	 * 创建带父亲指针的普通二叉树
	 * @return
	 */
	public static Node2 creatBTree2(){
		Node2 node1 = new Node2(1);
		Node2 node2 = new Node2(2);
		Node2 node3 = new Node2(3);
		Node2 node4 = new Node2(4);
		Node2 node5 = new Node2(5);
		Node2 node6 = new Node2(6);
		Node2 node7 = new Node2(7); 
		
		node5.left = node3;
		node3.parent = node5;
		node5.right = node7;
		node7.parent = node5;
		node3.left = node2;
		node2.parent = node3;
		node2.left = node1;
		node1.parent = node2;
		node3.right = node4;
		node4.parent = node3;
		node7.left = node6;
		node6.parent = node7;
		return node5;
	}
	/**
	 * 先序遍历递归版
	 * @param root
	 */
	public static void MLR(Node root){
		if(root == null){
			return;
		}
		System.out.print(root.value+" ");
		MLR(root.left);
		MLR(root.right);
	}
	/**
	 * 中序遍历递归版
	 * @param root
	 */
	public static void LMR(Node root){
		if(root == null){
			return;
		}
		LMR(root.left);
		System.out.print(root.value+" ");
		LMR(root.right);
	}
	/**
	 * 后续遍历递归版
	 * @param root
	 */
	public static void LRM(Node root){
		if(root == null){
			return;
		}
		LRM(root.left);
		LRM(root.right);
		System.out.print(root.value+" ");
	}
	
	/**
	 * 层次遍历
	 * @param root
	 */
	public static void levelTravel(Node root){
		if(root == null){
			return;
		}
		LinkedList<Node> list = new LinkedList<Node>();
		list.offer(root);
		Node node;
		while(list.size()>0){
			node = list.poll();
			System.out.print(node.value+" ");
			if(node.left != null){
				list.offer(node.left);
			}
			if(node.right != null){
				list.offer(node.right);
			}
		}
	}
	/**
	 * 寻找两个节点的最低公共祖先，二叉排序树
	 * @param root
	 * @param data1
	 * @param data2
	 * @return
	 */
	public static Node findCommonFather(Node root, int data1, int data2){
		if(root == null){
			return null;
		}
		Node node = root;
		while(node!=null){
			if(node.value > data1 && node.value > data2){
				node = node.left;
			}else if(node.value < data1 && node.value < data2){
				node = node.right;
			}else{
				return node;
			}
		}
		return null;
	}
	/**
	 * 寻找两个节点的最低公共祖先，普通二叉树有父指针
	 * @param root
	 * @param node1
	 * @param node2
	 * @return
	 */
	public static Node2 findCommonFather2(Node2 root, Node2 node1, Node2 node2){
		if(root == null){
			return null;
		}
		int len1 = 1;
		int len2 = 1;
		Node2 node11 = node1,node22 = node2;
		while(node11.parent !=null ){
			len1++;
			node11 = node11.parent;
		}
		while(node22.parent !=null ){
			len2++;
			node22 = node22.parent;
		}
		while(len1>len2){
			node1 = node1.parent;
			len1--;
		}
		while(len2>len1){
			node2 = node2.parent;
			len2--;
		}
		while(node1!=null  && node2!=null && node1 != node2){
			node1 = node1.parent;
			node2 = node2.parent;
		}
		if(node1 == node2){
			return node1;
		}else{
			return null;
		}
	}
	/**
	 * 寻找两个节点的最低公共祖先，普通二叉树
	 * @param root
	 * @param node1
	 * @param node2
	 * @return
	 */
	public static Node findCommonFather3(Node root, Node node1, Node node2){
		if(root == null){
			return null;
		}
		if(node1 == root || node2 == root){
			return root;
		}
		Node left = findCommonFather3(root.left, node1, node2);
		Node right = findCommonFather3(root.right, node1, node2);
		if(left !=null && right!=null){
			return root;
		}
		if(left==null){
			return right;
		}else{
			return left;
		}
		
	}
	
	/**
	 * 二叉查找树查找某个节点的路径
	 * @param root
	 * @param x
	 * @param list
	 */
	@SuppressWarnings("unchecked")
	public static void findPath(Node root, int x ,Stack<Integer> list){
		if(root == null){
			return ;
		}
		list.push(root.value);
		if(root.value == x){
			pathList = (Stack<Integer>) list.clone();
			return ;
		}
		if(root.left!=null){
			findPath(root.left, x, list);
		}
		
		if(root.right!=null){
			findPath(root.right, x, list);
		}
		list.pop();
	}
	
	/**
	 * 树的最大深度
	 * @param root
	 * @return
	 */

	public static int getMaxDeph(Node root){
		if(root == null){
			return 0;
		}
		int left = getMaxDeph(root.left);
		int right = getMaxDeph(root.right);
		return Math.max(left, right)+1;
	}
	
	/**
	 * 树的最小深度
	 * @param root
	 * @return
	 */
	public static int getMinDeph(Node root){
		if(root == null){
			return 0;
		}
		int left = getMinDeph(root.left);
		int right = getMinDeph(root.right);
		if(left == 0 && right ==0){
			return 1;
		}else if(left == 0 && right != 0){
			return right+1;
		}else if (left!=0 && right == 0){
			return left+1;
		}else{
			return Math.min(left, right)+1;
		}
	}
	
	/**
	 * 树的节点个数
	 * @param root
	 * @return
	 */
	public static int numOfNode(Node root){
		if(root == null){
			return 0;
		}
		int left = numOfNode(root.left);
		int right = numOfNode(root.right);
		return left+right+1;
	}
	
	/**
	 * 树的叶子节点的个数
	 * @param root
	 * @return
	 */
	public static int numOfLeaf(Node root){
		if(root == null){
			return 0;
		}
		if(root.left==null && root.right==null){
			return 1;
		}
		int left = numOfLeaf(root.left);
		int right = numOfLeaf(root.right);
		return left+right;
	}
	
	/**
	 * 树某一层节点的个数
	 * @param root
	 * @param level
	 * @return
	 */
	public static int getLevelNumOfNode(Node root, int level){
		if(root == null || level < 1){
			return 0;
		}
		if(level == 1){
			return 1;
		}
		int left = getLevelNumOfNode(root.left, level-1);
		int right = getLevelNumOfNode(root.right, level-1);
		return left+right;
	}
	
	/**
	 * 判断是否是平衡二叉树
	 * @param root
	 * @return
	 */
	public static boolean isBalanced(Node root){
		if(root == null){
			return true;
		}
		
		int left = getMaxDeph(root.left);
		int right = getMaxDeph(root.right);
		
		if(Math.abs(left-right)>1){
			return false;
		}else{
			return isBalanced(root.left) && isBalanced(root.right) && true;
		}
	}
	
	/**
	 * 判断是否是完全二叉树
	 * @param root
	 * @return
	 */
	public static boolean isAllTree(Node root){
		if(root == null){
			return false;
		}
		boolean result = true;
		boolean hasNoChild = false; 
		LinkedList<Node> list = new LinkedList<Node>();
		list.add(root);
		Node node;
		while(list.size()>0){
			node = list.remove();
			if(hasNoChild){
				if(node.left!=null || node.right!=null){
					result = false;
					break;
				}
			}else{
				if(node.left!=null && node.right!=null){
					list.add(node.left);
					list.add(node.right);
				}else if(node.left!=null && node.right==null){
					list.add(node.left);
					hasNoChild = true;
				}else if(node.left==null && node.left!=null){
					result = false;
					break;
				}else{
					hasNoChild = true;;
				}
			}
		}
		return result;
	}
	
	/**
	 * 判断两个树是否相等
	 * @param root1
	 * @param root2
	 * @return
	 */
	public static boolean isSimTree(Node root1, Node root2){
		if(root1 == null && root2 == null){
			return true;
		}
		if(root1 == null || root2 == null){
			return false;
		}
		if(root1.value != root2.value){
			return false;
		}
		boolean left = isSimTree(root1.left, root2.left);
		boolean right = isSimTree(root1.right, root2.right);
		
		return left && right;
	}
	
	/**
	 * 判断两个树是否互为镜像
	 * @param root1
	 * @param root2
	 * @return
	 */
	public static boolean isMirror(Node root1, Node root2){
		if(root1 == null && root2 == null){
			return true;
		}
		if(root1 == null  || root2 == null){
			return false;
		}
		boolean left = isMirror(root1.left, root2.right);
		boolean right = isMirror(root1.right, root2.left);
		return left && right;
	}
	
	/**
	 * 翻转树
	 * @param root
	 * @return
	 */
	public static Node convertTree(Node root){
		if(root == null){
			return null;
		}
		if(root.left!=null || root.right!=null){
			Node temp = null;
			temp = root.left;
			root.left = root.right;
			root.right = temp;
		}
		convertTree(root.left);
		convertTree(root.right);
		return root;
	}
	
	/**
	 * 通过前序遍历和中序遍历确定一个树
	 * @param pre
	 * @param mid
	 * @return
	 */
	public static Node buildTreeByPreAndMid(int[] pre, int[] mid){
		if(pre.length!=mid.length){
			return null;
		}
		Map<Integer,Integer> midMap = new HashMap<Integer,Integer>();
		int i = 0;
		for(int data : mid){
			midMap.put(data, i++);
		}
		
		return doBuildTreeByPreAndMid(pre,0,pre.length-1,mid,0,mid.length-1,midMap);
	}
	
	public static Node doBuildTreeByPreAndMid(int[] pre, int start1, int end1, int[] mid, int start2, int end2, Map<Integer,Integer> midMap){
		if(start2>end2){
			return null;
		}
		
		Node root = new Node(pre[start1]);
		int index = midMap.get(pre[start1]);
		
		root.left = doBuildTreeByPreAndMid(pre, start1+1, start1+index-start2, mid, start2, index-1, midMap);
		root.right = doBuildTreeByPreAndMid(pre, index+start1-start2+1, end1, mid, index+1, end2, midMap);
		return root;
	} 
	
	/**
	 * 根据中序遍历和后续遍历确定一个树
	 * @param mid
	 * @param post
	 * @return
	 */
	public static Node buildTreeByMidAndPost(int[] mid, int[] post){
		if(mid.length!=post.length){
			return null;
		}
		
		Map<Integer,Integer> midMap = new HashMap<Integer,Integer>();
		int i=0;
		for(int data : mid){
			midMap.put(data, i++);
		}
		
		return doBuildTreeByMidAndPost(mid,0,mid.length-1,post,0,post.length-1,midMap);
	}

	public static Node doBuildTreeByMidAndPost(int[] mid, int start1, int end1, int[] post, int start2, int end2,
			Map<Integer, Integer> midMap) {
		if(start1>end1){
			return null;
		}
		Node root = new Node(post[end2]);
		int index = midMap.get(post[end2]);
		root.left = doBuildTreeByMidAndPost(mid, start1, index-1, post, start2, index-1+start2-start1, midMap);
		root.right = doBuildTreeByMidAndPost(mid, index+1, end1, post, index+start2-start1, end2-1, midMap);
		
		return root;
	}
	/**
	 * 根据中序遍历和层次遍历确定一个树
	 * @param mid
	 * @param level
	 * @return
	 */
	public static Node buildTreeByMidAndLevel(int[] mid,int[] level){
		if(mid.length!=level.length){
			return null;
		}
		
		Map<Integer,Integer> midMap = new HashMap<Integer,Integer>();
		int i = 0;
		for(int data : mid){
			midMap.put(data, i++);
		}
		
		return doBuildTreeByMidAndLevel(mid,0,mid.length-1,level,midMap);
	}

	public static Node doBuildTreeByMidAndLevel(int[] mid, int start1, int end1, int[] level,
			Map<Integer, Integer> midMap) {
		if(start1>end1 || level.length == 0){
			return null;
		}
		Node root = new Node(level[0]);
		int index = midMap.get(level[0]);
		
		Map<Integer,Integer> tempMidLeft = new HashMap<Integer,Integer>();
		for(int i = start1;i<=index-1;i++){
			tempMidLeft.put(mid[i], i);
		}
		int[] temp = new int[index-start1];
		int i=0;
		for(int data : level){
			if(tempMidLeft.containsKey(data)){
				temp[i++] = data;
			}
		}
		
		Map<Integer,Integer> tempMidRight = new HashMap<Integer,Integer>();
		for(int j = index+1;j <= end1;j++){
			tempMidRight.put(mid[j], j);
		}
		int[] temp2 = new int[end1-index];
		int j=0;
		for(int data : level){
			if(tempMidRight.containsKey(data)){
				temp2[j++] = data;
			}
		}
		
		root.left = doBuildTreeByMidAndLevel(mid, start1, index-1, temp, midMap);
		root.right = doBuildTreeByMidAndLevel(mid, index+1, end1, temp2, midMap);
		return root;
	}
	
	/**
	 * 树中插入一个节点
	 * @param root
	 * @param x
	 * @return
	 */
	public static Node insertNode(Node root, int x){
		if(root == null){
			return null;
		}
		Node node  = new Node(x);
		Node tmp = root;
		Node last = null;
		while(tmp!=null){
			last = tmp;
			if(tmp.value>x){
				tmp = tmp.left;
			}else{
				tmp = tmp.right;
			}
		}
		if(last!=null){
			if(last.value>x){
				last.left = node;
			}else{
				last.right = node;
			}
		}
		return root;
	}
	
	/**
	 * 获取累加值为x的所有路径
	 * @param root
	 * @param x
	 */
	public static void findAllPath(Node root, int x){
		if(root == null){
			return ;
		}
		int currentSum = 0;
		Stack<Node> stack = new Stack<Node>();
		doFindAllPath(root, x, currentSum, stack);
	}
	
	public static void doFindAllPath(Node root, int x , int currentSum, Stack<Node> stack){
		if(root == null){
			return ;
		}
		currentSum += root.value;
		stack.push(root);
		if(currentSum == x){
			for(Node node : stack){
				System.out.print(node.value+" ");
			}
			System.out.println();
		}
		
		if(currentSum < x){
			doFindAllPath(root.left, x, currentSum, stack);
			doFindAllPath(root.right, x, currentSum, stack);
		}
		stack.pop();	
	}
	
	/**
	 * 获取位于两个值范围内的所有节点，按升序排列
	 * @param root
	 * @param a
	 * @param b
	 */
	public static void findNodeBetweenAAndB(Node root, int a, int b){
		if(root == null){
			return ;
		}
		Stack<Node> stack = new Stack<Node>();
		doFindNodeBetweenAAndB(root, a, b, stack);
		for(Node node : stack){
			System.out.print(node.value+" ");
		}
	}
	
	public static void doFindNodeBetweenAAndB(Node root, int a, int b, Stack<Node> stack){
		if(root == null){
			return;
		}
		if(a > root.value){
			doFindNodeBetweenAAndB(root.left, a , b, stack);
		}
		if(a <= root.value  && root.value <= b){
			doFindNodeBetweenAAndB(root.left, a , b, stack);
			stack.push(root);
			doFindNodeBetweenAAndB(root.right, a , b, stack);
		}
		if(root.value > b){
			doFindNodeBetweenAAndB(root.left, a , b, stack);
		}
		
	}
	/**
	 * 判断是否是排序二叉树
	 * @param root
	 * @return
	 */
	public static boolean isBST(Node root){
		if(root == null){
			return true;
		}
		
		if(root.left!=null && root.left.value >= root.value){
			return false;
		}
		if(root.right!=null && root.right.value <=root.value){
			return false;
		}
		return isBST(root.left) && isBST(root.right);
	}
}

class Node{
	Node left;
	Node right;
	int value;
	public Node(int value) {
		this.value = value;
	}
}

class Node2{
	Node2 left;
	Node2 right;
	Node2 parent;
	int value;
	public Node2(int value) {
		this.value = value;
	}
}

